Automatic discovery of physical topology information plays a crucial role in enhancing the manageability of modern IT infrastructures. The problem of determining the physical topology of an IT infrastructure primarily occurs in the context of network management when a failure in an IT infrastructure needs to be localized. To this end, topology maps of IT infrastructures are built by means of topology discovery programs which are usually integrated into IT infrastructure management platforms.
Physical network topology refers to the characterization of the physical connectivity relationships that exist among entities in an IT infrastructure. Discovering the physical layout and interconnections of network elements is a prerequisite to many critical network management tasks, including reactive and proactive resource management, event correlation, and root-cause analysis. Given the dynamic nature of today's IT infrastructures, keeping track of topology information manually is a daunting (if not impossible) task. Thus, effective algorithms for automatically discovering physical network topology are necessary. Earlier work has typically concentrated on discovering logical (i.e. layer-3) topology, which implies that the connectivity of all layer-2 elements (switches and bridges) is ignored. For example, consider a fault monitoring and analysis application running on a central IT infrastructure management platform. Typically, a single fault in the network will cause a flood of alarm signals emanating from different interrelated network elements. Knowledge of element interconnection is essential to filter out secondary alarm signals and correlate primary alarms to pinpoint the original source of failure in the network.
Furthermore, a full physical map of the network enables a proactive analysis of the impact of link and device failures. Early identification of single points of failure that could disrupt a large fraction of the user community allows the network manager to improve the survivability of the network (e.g., by adding alternate routing paths) before outages occur.
Despite the critical role of topology information in enhancing the manageability of modern IP networks, none of the network management platforms available on the market today offers a general-purpose tool for automatic discovery of physical IP network connectivity. Most systems (including Hewlett Packard's OpenView Network Node Manager) feature an IP (Internet Protocol) mapping functionality for automatically discovering routers and subnets and generating a network (i.e. ISO layer-3) topology showing the router-to-router interconnections, router interface-to-subnet relationships and layer-3 addressable end devices. Determining a layer-3 topology is comparatively easy since routers need to be explicitly aware of their neighbor routers in order to perform their basic function, namely forwarding IP packets to other routers and IP addressable end devices. Therefore, standard routing information is adequate to capture and represent layer-3 connectivity. However, layer-3 topology only covers a small fraction of the interrelationships in an IP network, since it fails to capture the complex interconnections of layer-2 network elements (e.g., switches and bridges) that are included in all subnets.
The lack of automated solutions for capturing physical (i.e. layer-2) topology information means that network managers are routinely forced to manually input such information for each management tool that they use. Given the dynamic nature and the ever-increasing complexity of today's IT infrastructures, keeping track of topology information is a daunting (if not impossible) task. This situation clearly mandates the development of effective, general-purpose algorithmic solutions for automatically discovering the up-to-date physical topology of an IP network.
SNMP-based algorithms for automatically discovering network layer (i.e. layer-3) topology are featured in many common network management tools, such as Hewlett Packard's OpenView and IBM's Tivoli. Other commercially available tools for discovering layer-3 network topology using SNMP include Actualit's Optimal Surveyor and the Dartmouth Intermapper.
Recognizing the importance of layer-2 topology, a number of vendors have recently developed proprietary tools and protocols for discovering physical network connectivity, such as Cisco's Discovery Protocol (CDP), which is an ISO-OSI layer-2 network protocol used by Cisco routers to obtain protocol addresses of nearby devices. CDP runs on all Cisco devices, but not on devices of other manufacturers. Therefore, CDP cannot be employed in networks with elements of different vendors. CDP can be used on all media that support Subnetwork Access Protocol (SNAP): this includes Ethernet, Frame Relay and Asynchronous Transfer Mode (ATM). Each device which is configured for CDP periodically sends messages (advertisements) to a multicast address. Each device sends to at least one further address at which it may receive SNMP messages. The advertisements contain information about the time to life and the holdtime of the packet. The default value for a Cisco router is 60 seconds.
Normally, the topology of only a part of an IT infrastructure needs to be discovered. Administrators are able to control the scope of the topology function. This includes restricting use to certain sub-networks or restricting the routes used by specifying “boundary systems” (e.g., gateway routers to a public network). Failure to limit a topology-discovery process can overload a network and the higher-level network in which it participates.
In U.S. Pat. No. 6,516,345 a method for determining actual physical topology of network devices in a network is disclosed. A discovery mechanism determines a set of network addresses for identifying devices within a network. Based on the set of network addresses, the discovery mechanism identifies a group of devices that are associated with the network. Layer-2 and layer-3 configuration information is gathered from the group of devices to identify possible neighboring devices within the network.
In U.S. Pat. No. 6,003,074 a method is disclosed which enables a mapping of devices that are interconnected in a subnetwork between a first node and a second node. Initially, the method determines a subnetwork that includes both the first and second nodes and devices comprising the subnetwork. Next, the method determines a list of devices in the subnetwork which have seen traffic from the first node, and port identities on which the traffic has been experienced. A map between the first and the second node is obtained by selecting intermediate devices and figuring out where they are located by comparing at which ports traffic has been experienced.
U.S. Pat. No. 5,729,685 discloses an asynchronous transfer mode (ATM) network or the like employing a method and apparatus for automatically determining the topology of the network. The method and apparatus provides link advertisement messages for each switch in the network transmitting on each of its ports (without processing intervention by intermediate switches). The link advertisement messages are received by neighbor switches and forwarded to a topology manager. The topology manager constructs network topology profile information based on received link advertisement messages. Further, the topology manager is able to verify bidirection links based on the link advertisement messages received.
U.S. Pat. No. 5,297,138 discloses a method of determining the physical topology of devices on a network. All the devices on the network are identified. A first device is selected. For each port of the first device a connection structure is recursively determined for all devices which communicate to the first device through the port.
U.S. Pat. No. 6,377,987 discloses a mechanism for determining the actual physical topology of network devices in a network. To determine a physical topology, a discovery mechanism determines a set of network addresses for identifying devices within a network. Based on the set of network addresses, the discovery mechanism identifies a group of devices that are associated with the network. Layer 2 and layer 3 configuration information is gathered from the group of devices to identify possible neighboring devices within the network. The configuration information is then processed to generate topology information that identifies true neighboring devices and the actual links that exist between each of the neighboring devices. The mechanism eliminates misleading information and prevents generation of incorrect topologies.
U.S. Pat. No. 6,108,702 discloses a monitoring system for determining accurate topology features of a network, and methods of operating the monitoring system. In the preferred embodiment, the system creates an accurate topology map of a given network by: obtaining a list of managed network devices; identifying trunk ports, link channel ports, and trunk channel ports; identifying link port and node ports; determining connections between the ports; storing the collected information; and displaying the network topology.
U.S. Pat. No. 5,708,772 discloses a computer-implemented method and apparatus for determining a topology of a network. Signals are received from all source hubs in the network, wherein each of the signals contains connection information for the source hubs including destination hubs to which the source hubs are coupled, and a corresponding connection port on the source hubs through which the destination hubs are coupled. The connection information is processed by locating all unitary connections in the connection information. Subsequently, if the connection information is not empty and there are additional unitary connections in the connection information, then the foregoing steps are repeated until there are no more unitary connections or the processed connection information is empty.